package org.example.algorithm.matrix;

//74. 搜索二维矩阵
public class SearchMatrix2Solution {
    public static void main(String[] args) {
        int[][] matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        //int[][] matrix = {{1,3}};
        SearchMatrix2Solution solution = new SearchMatrix2Solution();
        boolean ans = solution.searchMatrix(matrix, 3);
        System.out.println(ans);
    }

    //二分法
    public boolean searchMatrix2(int[][] matrix, int target) {
        int row = matrix.length;
        int col = matrix[0].length;
        if (row == 0) {
            return false;
        }
        int left = 0;
        int right = row * col - 1;
        while (left <= right) {
            int middle = (left + right) >> 1;
            int temp = matrix[middle / col][middle % col];
            if (temp == target) {
                return true;
            } else if (temp > target) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return false;
    }

    //排除法（从右上角开始遍历）
    public boolean searchMatrix1(int[][] matrix, int target) {
        int i = 0;
        int j = matrix[0].length - 1;
        while (i<matrix.length && j>=0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] > target) {
                j--;
            } else {
                i++;
            }
        }
        return false;
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        int goalRow = findRow(matrix, row, target);
        if (goalRow == -1) {
            return false;
        }
        if (goalRow == Integer.MIN_VALUE) {
            return true;
        }
        return findInRow(matrix, goalRow, target);
    }

    private int findRow(int[][] matrix, int row, int target) {
        int low = 0;
        int high = row - 1;
        while (low <= high) {
            int middle = (low + high) >> 1;
            if (matrix[middle][0] == target) {
                return Integer.MIN_VALUE;
            } else if (matrix[middle][0] < target) {
                low = middle + 1;
            } else if (matrix[middle][0] > target) {
                high = middle - 1;
            }
        }
        return high;
    }

    private boolean findInRow(int[][] matrix, int goalRow, int target) {
        int left = 0;
        int right = matrix[goalRow].length - 1;
        while (left <= right) {
            int middle = (left + right) >> 1;
            if (matrix[goalRow][middle] == target) {
                return true;
            } else if (matrix[goalRow][middle] > target) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return false;
    }
}
